package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//39. 组合总和
//
//给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
//candidates 中的数字可以无限制重复被选取。
//
//说明：
//
//所有数字（包括 target）都是正整数。
//解集不能包含重复的组合。 
//示例 1:
//
//输入: candidates = [2,3,6,7], target = 7,
//所求解集为:
//[
//  [7],
//  [2,2,3]
//]
//示例 2:
//
//输入: candidates = [2,3,5], target = 8,
//所求解集为:
//[
//  [2,2,2,2],
//  [2,3,3],
//  [3,5]
//]


public class Solution039 {
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
        	return res;
        }
        
        dfs(candidates, target, res, 0, 0, new ArrayList<Integer>());
        return res;
    }
	
	private void dfs(int[] candidates, int target, List<List<Integer>> res, int start, int sum, List<Integer> path) {
		if (sum > target) {
			return;
		} else if (sum == target) {
			res.add(new ArrayList<>(path));
			return;
		}
		
		for (int i=start; i<candidates.length; i++) {
			path.add(candidates[i]);
			dfs(candidates, target, res, i, sum+candidates[i], path);
			path.remove(path.size()-1);
		}
		
	}
}
